package problem496;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

//496.下一个更大元素I
//https://leetcode.cn/problems/next-greater-element-i/

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums1.length, m = nums2.length;
        int[] ret = new int[n];
        for(int i = m-1; i>=0; i--) {
            while(!stack.isEmpty() && nums2[i] >= stack.peek()) {
                stack.pop();
            }
            if(!stack.isEmpty()) map.put(nums2[i], stack.peek());
            stack.push(nums2[i]);
        }
        for(int i = 0; i<n; i++) {
            ret[i] = map.getOrDefault(nums1[i], -1);
        }
        return ret;
    }
}